1. Field of the Invention
The present invention relates generally to deformable object modeling and, more particularly, to a novel long elements method (LEM) of real time simulation of deformable objects in a virtual environment.
2. Description of the Related Art
Deformable object modeling has been known in the art for decades and is widely utilized in fields such as engineering, computer-aided design (CAD), and entertainment. Particularly in a virtual reality (VR) computing environment, the ability to model and manipulate deformable objects is essential to many applications. As such, graphic display of deformable objects has been extensively studied in computer graphics and a number of methods have been proposed accordingly. These prior art methods ranging from non-physical methods, where individual or groups of control points or shape parameters are manually adjusted to shape editing and design, to methods based on continuum mechanics, which account for material properties and internal and external forces on object deformation.
As computational power increases, the ability to simulate physically based deformable models with enhanced multi-modal interactivity, i.e., using graphic and haptic interfaces to manipulate and to change the topology of deformable objects in real time, becomes even more desirable.
A major application area for this desirable real time physically based deformable object modeling with enhanced multi-modal interactivity is the simulation of biomaterials. Physical modeling of biomaterials has a broad range of applications ranging from understanding how soft and hard tissue respond under loading, to patient-specific planning of reconstructive procedures, to the training of surgical skills, and much more. Interaction with these models is necessary in order to impose conditions of interest, to examine results and alternative solutions, to learn surgical procedures by performing them in simulation.
Given the intrinsic physical nature of these models it is desirable to have direct physical interactions with them. “Haptic” or direct physical interaction with simulated objects and/or subjects has become possible in recent years because of advances in haptic (touch) interface technology, with devices now commercially available from companies such as the Immersion Corp. and SensAble Technologies.
Not only does haptic technology enable convenient and expressive direct interactions with biomechanical simulations, it is also well suited to the intrinsically three-dimensional (3D) nature of biological models. Further, it links physical intuition to understanding of models, and, in training and rehearsal situations, it greatly enhances the learning process, much as in music training where one actually learns better and faster with the feeling and fingering of an instrument's keys.
Modeling the biomechanics of muscles, tissues, and organs is intrinsically a computationally difficult undertaking—doing so at haptically real-time rates requires significant computational resources and algorithmic finesse.
What is more, simulation methods must balance between two conflicting demands. Simulation for deformable objects can be classified by the degree of interaction they allow and their accuracy. The usefulness of a simulation method is defined by these two conflicting demands. Models focusing on interactiveness must have low latency and are based in some internal structure suitable for topological changes in real time. Models focusing on accuracy have the precision of their results limited only by some scale factor and the computational power.
Unfortunately, these seemingly conflicting classifications frequently go together. Interactive methods, such as the mass-spring method disclosed by G. Miller in “The motion dynamics of snake and worms”, are mainly non-physical and often inaccurate, as pointed out by Zhuang et al. in “Haptic Interaction with Global Deformations”, which is hereby incorporated herein by reference. Accurate physically based methods, such as the Finite Elements Method (FEM), are typically simulated off-line and not in real time. What is more, modifying these methods to achieve real time performance usually compromises their accuracy and/or their interactiveness.
Simulation methods can also be classified in accordance with additional aspects. For example, deformations can be dynamic or static, global or local. Models can be elastic or visco-elastic, linear or nonlinear, surface or volumetric. Collision detection and handling can be implemented using different approaches. All these aspects define the way a simulation will behave, its accuracy and performance, and the kind of applications for which it will be well suited.
The distinction between dynamic and static methods is of particular interest here. Dynamic methods simulate the evolving state of a physical system. The bodies have mass and energy distributed throughout. Differential equations and a finite state vector define each model. Numerical integration techniques approximate the system state (position and velocity) at discrete time steps.
In static methods, such physical system is described by equilibrium equations or closed-form expressions, such as those taught by G. S. Chirikjian in “Closed-form primitives for generating volume preserving deformations”, which is hereby incorporated herein by reference. These static equations are solved to find a static solution at each time step. In static and quasi-static methods, the time and the system state are usually not considered.
Thus, a state-based approach, i.e., a dynamic method, should be used for more comprehensive and accurate simulations of a deformable object/medium/subject, given significant internal dynamics of the deformable object, as well as the dynamics of the movements (translations and rotations) of the object in space. Note static and quasi-static methods are nonetheless useful in applications where the objects deform but do not move, or move slowly, and the deformable media is highly damped.
A number of schemes implementing these methods for deformable modeling have been developed, most notable ones are: mass-spring damper (MSD) systems, the boundary element method (BEM), the finite difference method (FDM), and the finite element method (FEM), as described by Wu et al. in “Adaptive Nonlinear Finite Elements for Deformable body simulation using dynamic progressive meshes”, which is hereby incorporated herein by reference. As is well known in the art and according to Wu et al., these prior art methods have either used approximate methods that are not physically accurate or linear methods that do not produce reasonable global behavior.
For example, particle-based techniques are usually unstable and damping is extensively used to bring the system into a global equilibrium. In a particle-based simulation, damping and other constraints lead to a stiffer system, demanding shorter time steps to achieve stability. The number and distribution of particles is also a source of problems. Larger meshes increase the stiffness of the system and become computationally very expensive. Smaller meshes increase inaccuracies and difficult to preserve volume. Uneven distribution of particles may easily generate unstable interaction forces and non-smooth graphical deformations.
Finite element based methods generally produce globally accurate behavior but are usually too computationally expensive to be simulated in real-time. Pre-computation and condensation can be used to achieve real time rendering rates but changes in topology (re-meshing) demand an update of the stiffness matrix making the pre-computed data useless.
To overcome these deficiencies, Wu et al. described an adaptive meshing scheme based on dynamic progressive meshes (DPM) using nonlinear finite elements. The DPM method has several limitations. For example, it relies on a hierarchy built offline. Thus, an initial detailed mesh is the limit that can be achieved in online refinement. Also, its tree structure has directionality and cannot split a node in any arbitrary direction locally. Consequently, the refined local region does not necessarily achieve optimal mesh quality.
What is needed in the art is a new, computationally simple, fast, portable, and efficient simulation methodology capable of achieving real time performance and optimal mesh quality without compromising either accuracy or interactiveness, overcoming prior art drawbacks and limitations.